package dp

// 给你一个整数 n ，
// 求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？
// 返回满足题意的二叉搜索树的种数。
func numTrees(n int) int {
	dp:=make([]int,n+1)
	dp[0]=1
	for i:=1;i<=n;i++{
		for j:=1;j<=i;j++{
			dp[i]+=dp[j-1]*dp[i-j]
		}
	}
	return dp[n]
}
/*  只关注形态
dp[i] i个节点的bst种数
dp[0] = 0
dp[1] = 1
dp[2] = 2
3 为头部 其余形态等于只有两个节点的情况
1 为头部 
2 为头部 只有一种  左右子树等于一个节点的情况
dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

有2个元素的搜索树数量就是dp[2]。

有1个元素的搜索树数量就是dp[1]。

有0个元素的搜索树数量就是dp[
dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

dp[i] 1-i节点组成的二叉搜索树个数
所以 dp[i] += dp[j为头结点的左子树节点数量]*dp[j为头结点右子树节点数量]   j需要遍历
dp[i] += dp[j-1]*dp[i-j]   i-j是比j大的数字个数  j-1是比j小的个数
*/